//
// Created by LIN on 25-8-24.
//

#ifndef BINARYSEARCHTREE_H
#define BINARYSEARCHTREE_H

#include <print>
using namespace std;

template<class K>
struct BinarySearchTreeNode
{
    K key_;
    BinarySearchTreeNode* left_;
    BinarySearchTreeNode* right_;

    explicit BinarySearchTreeNode(const K& key)
        : key_(key)
        , left_(nullptr)
        , right_(nullptr)
    {}
};

template<class K>
class BinarySearchTree
{
    using Node = BinarySearchTreeNode<K>;

public:
    bool insert(const K& key)
    {
        if (root_ == nullptr)
        {
            // 当根为空时，新建一个节点
            root_ = new Node(key);
            return true;
        }

        // 查找插入位置
        Node* parent = nullptr;
        Node* current = root_;

        while (current)
        {
            // 当键值大于当前节点，向右子树查找
            if (key > current->key_)
            {
                parent = current;
                current = current->right_;
            }
            // 当键值小于当前节点，向左子树查找
            else if (key < current->key_)
            {
                parent = current;
                current = current->left_;
            }
            // 键值等于当前节点，则插入失败
            else
            {
                return false;
            }
        }

        // 创建新节点
        current = new Node(key);
        // 将新节点连接到父节点上
        if (key > parent->key_)
            parent->right_ = current;
        else
            parent->left_ = current;

        return true;
    }

    bool find(const K& key)
    {
        Node* current = root_;

        while (current)
            if (key > current->key_)
                current = current->right_;
            else if (key < current->key_)
                current = current->left_;
            else
                return true;
        return false;
    }

    bool erase(const K& key)
    {
        Node* parent = nullptr;
        Node* current = root_;

        while (current)
        {
            if (key > current->key_)
            {
                parent = current;
                current = current->right_;
            }
            else if (key < current->key_)
            {
                parent = current;
                current = current->left_;
            }
            // 找到删除节点
            else
            {
                // 情况1：需要删除的节点左子树为空
                if (current->left_ == nullptr)
                {
                    // 当前节点不是根节点
                    if (current != root_)
                    {
                        // 如果当前节点是父节点的左子树节点
                        if (current == parent->left_)
                            parent->left_ = current->right_;
                        // 如果当前节点是父节点的右子树节点
                        else
                            parent->right_ = current->right_;
                    }
                    else
                        root_ = current->right_;

                    delete current;
                }
                else if (current->right_ == nullptr)
                {
                    if (current != root_)
                    {
                        if (current == parent->left_)
                            parent->left_ = current->left_;
                        else
                            parent->right_ = current->left_;
                    }
                    else
                        root_ = current->left_;

                    delete current;
                }
                else
                {
                    Node* minRightParent = current;
                    Node* minRight = current->right_;

                    while (minRight->left_)
                    {
                        minRightParent = minRight;
                        minRight = minRight->left_;
                    }

                    current->key_ = minRight->key_;

                    if (minRight == minRightParent->left_)
                        minRightParent->left_ = minRight->right_;
                    else
                        minRightParent->right_ = minRight->right_;

                    delete minRight;
                }
                return true;
            }
        }
        return false;
    }

    void in_order()
    {
        in_order_(root_);
        print("\n");
    }

private:
    void in_order_(Node* root)
    {
        if (root == nullptr)
            return;
        in_order_(root->left_);
        print("{} ", root->key_);
        in_order_(root->right_);
    }

    Node* root_ = nullptr;
};

#endif /* BINARYSEARCHTREE_H */
